題目:

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

給定一數字字串,每一數字都有其可能對應到的字母
求出此數字字串可能對應到的所有字母字串組合
而數字對字母的關係如下:
2:"abc",3:"def",4:"ghi",5:"jkl",6:"mno",7:"pqrs",8:"tuv",9:"wxyz"
ex:input: digits = "23"=>output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

這題我用有點dp(?的感覺下去做

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        ans=[]
        d={"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
        
        def x(s,ans):
            r=[]
            if ans==[]:
                for j in d[s]:
                    r.append(j)
            else:
                for i in range(len(ans)):
                    for j in d[s]:
                        r.append(ans[i]+j)
            return r
        
        for i in digits:
            ans=x(i,ans)
            
        return ans

先設立字典(d)確立數字和字母的對應關係
接著一空陣列ans,和一函數x
此函數需傳入一數字字元(i)和陣列(ans)
若陣列為空,則將所有i對應到的字母字元個別放入一空陣列r
結束後回傳r
若陣列不為空,則將所有i對應到的字母字元依次加入ans內所有元素尾端後
將改動後的元素放入r,結束後回傳r
ex:"23":["a","b","c"]=>["ad","ae","af","bd","be","bf","cd","ce","cf"]
所以我們要做的就是從數字字串第一個字元開始讓ans等於x(字元,ans)
不斷拓展可能
直到最後一個字元,我們就有數字字串對應到的所有可能字母字串組合了
最後執行時間33ms(faster than 90.56%)

今天比較忙就只更兩題啦

那我們下題見